package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.concurrent.*;

/**
 * 希尔排序 插入排序的升级版本
 * <p>
 * 8 9 1 7 2 3 5 4 6 0
 * 1 2 3 4 5 1 2 3 4 5     编号相同的是一组  每组进行 插入排序  组=length/2=5
 * <p>
 * 3 5 1 6 0 8 9 4 7 2     一轮后的数据
 * 1 2 1 2 1 2 1 2 1 2     组=5/2=2
 * <p>
 * 0 2 1 4 3 5 7 6 9 8
 * 1 1 1 1 1 1 1 1 1 1     组=2/1 =1  进行插入排序 可以达到有序了  这就解决了插入排序的问题
 * <p>
 * 希尔排序时 对有序序列在插入时采用交换法，
 * 移动法。
 */
public class ShellSort {

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        int size = 80000;
        ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(5, 10, 15, TimeUnit.SECONDS, new ArrayBlockingQueue<>(5), Executors.defaultThreadFactory(),
                new ThreadPoolExecutor.CallerRunsPolicy());

        // 异步执行
        CompletableFuture<Void> runAsync = CompletableFuture.runAsync(() -> {

            int[] testArr = new int[size];
            for (int i = 0; i < testArr.length; i++) {
                testArr[i] = (int) (Math.random() * size);
            }
            Instant start = Instant.now();
            shellSortJH(testArr);       // 7218 毫秒
            Instant end = Instant.now();
            System.out.println("交换：" + Duration.between(start, end).toMillis());
            //        System.out.println(Arrays.toString(testArr));

        }, threadPoolExecutor);

        CompletableFuture<Void> runAsync1 = CompletableFuture.runAsync(() -> {
            int[] testArr = new int[size];
            for (int i = 0; i < testArr.length; i++) {
                testArr[i] = (int) (Math.random() * size);
            }
            Instant start = Instant.now();
            shellSortYD(testArr);       // 17 毫秒
            Instant end = Instant.now();
            System.out.println("移动：" + Duration.between(start, end).toMillis());
//            System.out.println(Arrays.toString(testArr));
        }, threadPoolExecutor);

        // 等待上面异步执行执行完成 可以等待多个 必须得等上面的两个异步任务执行完成才能执行下面的事情
        CompletableFuture.allOf(runAsync1, runAsync).get();  // 不等待的话 上面两个和main就会随机执行
        System.out.println("执行完成");
        threadPoolExecutor.shutdown();


    }

    /**
     * 希尔排序 通过交换   很慢
     *
     * @param arr
     */
    public static void shellSortJH(int[] arr) {

        // 计算步长的循环 当步长<=0 就退出循环
        for (int step = arr.length / 2; step > 0; step = step / 2) {

            // 从步长开始往后遍历
            for (int i = step; i < arr.length; i++) {
                // 遍历这一组（前几个元素）
                for (int j = i - step; j >= 0; j -= step) {  // 将一组中的前几个元素进行比较
                    if (arr[j] > arr[j + step]) {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
        }
    }

    /**
     * 希尔排序 通过移动
     *
     * @param arr
     */
    public static void shellSortYD(int[] arr) {
        for (int step = arr.length / 2; step > 0; step = step / 2) {

            // 从一个步长间隔开始遍历
            // 就相当于从每组的第二个数开始遍历
            // 然后这里的移动法 就是插入排序（待插入的数据 和前面的有序列表进行比较 然后将有序列表往后移动 最后将待插入的数据插入到需要插入的位置）
            for (int i = step; i < arr.length; i++) {
                int insertValue = arr[i];
                int insertIndex = i - step;
                while (insertIndex >= 0 && arr[insertIndex] > insertValue) {
                    arr[insertIndex + step] = arr[insertIndex]; // 将数据往后移动step个位置
                    insertIndex -= step;  // 将索引往前移动step
                }
                if (insertIndex + step != i) {    // 判断待插入位置是否就是待插入元素所在的位置
                    arr[insertIndex + step] = insertValue;
                }
            }
        }
    }
}
